Motion searching is an important part of contemporary video encoding, and is known to be a high bandwidth, memory intensive activity. Typically, block based motion estimation is carried out, in which a current frame is subdivided into blocks of pixels. Each of these blocks (also referred to herein as a source block) is then compared to a reference frame (which may for example be the preceding frame) to find a best-matching block therein. The displacement from the location of this best-matching block to the current source block defines a motion vector, which is used by the video encoder to encode the source block by reference to that best matching block, using the motion vector together with further information representing any residual difference between the blocks.
Due to the computational demands of motion searching, in particular the memory access bandwidth requirements, it is known to perform a motion search in more than one step, initially carrying out a rough search which identifies an approximate motion vector, followed by a more detailed search to refine the results of the rough search. In this context, it is known for the rough search to search discrete positions in the reference frame or search a down-sampled version of the reference frame. Down-sampling is the process of generating an image of lower resolution from a higher resolution image. Performing motion vector searching using down-sampled images has the advantage of reducing memory access bandwidth, but at the cost of lower accuracy in the motion search.
It is further known for motion searches to be carried out in more than two steps, in a multi-resolution motion search. For example in “A Fast Hierarchical Motion Vector Estimation Algorithm Using Mean Pyramid”, Kwon Moon Nam et al, IEEE Trans. Circuits and Systems for Video Technology, Volume 5, pp. 344-351, April 1993, a multi-stage motion search is described in which the motion search is broken down into several stages of progressive resolutions.
Hence, although down-sampling can avoid the high bandwidth requirements of a full resolution search, it suffers from a degradation in motion vector estimation accuracy resulting from the lower resolution of the down-sampled search image. More severely, when the full resolution image contains high frequency detail, the loss of such high frequency components of the image can result in the calculation of a motion vector from the down-sampled image that is significantly different from that which would have been calculated from the full resolution image.
Hence, it would be desirable to provide an improved technique for motion vector estimation in a video encoder with improved accuracy, yet without the high bandwidth requirements of a full resolution search.